package com.smh.a01queryDemo01;

public class ErFenFaSearchDemo2 {
    public static void main(String[] args) {

        int[] arr ={1,2,3,4,5,6,7,9,10};
        System.out.println(binarySearch(arr,12));

    }

    public static int binarySearch(int[] arr,int num){
        int min = 0;
        int max = arr.length-1;
        while (min<=max){
            int mid =(min+max)/2;
            int a = arr[mid];
            if (a==num){
                return mid;
            }else if (a<num){
                min=mid+1;
            }else {
                max=mid-1;
            }
        }
        return -1;
    }

    //适用于数据分配均匀
    //插值法
    public static int binarySearch1(int[] arr,int num){
        int min = 0;
        int max = arr.length-1;
        while (min<=max){
            int mid =min+(num-arr[min])/(arr[max]-arr[min])*(max-min);
            int a = arr[mid];
            if (a==num){
                return mid;
            }else if (a<num){
                min=mid+1;
            }else {
                max=mid-1;
            }
        }
        return -1;
    }
    //斐波那契查找
    public static int binarySearch2(int[] arr,int num){
        int min = 0;
        int max = arr.length-1;
        while (min<max){
            int mid =0;//没写
            int a = arr[mid];
            if (a==num){
                return mid;
            }else if (a<num){
                min=mid+1;
            }else {
                max=mid-1;
            }
        }
        return -1;
    }

}
